package DisjointSetUnion;

/**
 * 一个字符串只交换两个字母得到的字符串和原来的相似
 * 把所有相似的字符串分到同一组
 * example: ['ab', 'ba', 'abc', 'abd', 'acb']
 * -> ['abe','bae'] ['abd'] ['abc','acb']
 */
public class SimilarStringGroups {
    public static void main(String[] args) {
        System.out.println(numSimilarGroups(new String[]{"abc", "acb", "bac", "bca", "cab", "cba"}));
    }

    // 单词最多300个
    public static int max_n = 301;

    public static int[] originator = new int[max_n];

    public static int sets;


    public static void build(int n) {
        for (int i = 0; i < n; i++) {
            originator[i] = i;
        }
        sets = n;
    }

    public static int find(int i) {
        if (i != originator[i]) {
            originator[i] = find(originator[i]);
        }
        return originator[i];
    }

    public static void union(int x, int y) {
        int ox = find(x);
        int oy = find(y);

        if (ox != oy) {
            originator[ox] = oy;
            sets--;
        }
    }

    public static int numSimilarGroups(String[] strings) {
        int n = strings.length;
        int m = strings[0].length();
        build(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (find(i) != find(j)) {
                    // 判断两个字符串是否相似
                    int diff = 0;
                    // 跳出条件: 还有字符 && 字符差异数目小于 < 3
                    for (int k = 0; k < m && diff < 3; k++) {
                        if (strings[i].charAt(k) != strings[j].charAt(k)) {
                            diff++;
                        }
                    }
                    if (diff == 0 || diff == 2) {
                        // 相似 or 相等，合并集合
                        union(i, j);
                    }
                }
            }
        }
        return sets;
    }
}
